package com.terry.test3;

import java.util.*;

/**
 * 【区间交集】给定一组闭区间，其中部分区间存在交集。任意两个给定区间的交集，称为公共区间(如:[1,2],[2,3]的公共区间为[2,2]，[3,5],[3,6]的公共区间为
 * [3,5])。公共区间之间 若存在交集，则需要合并(如:[1,3],[3,5]区间存在交集[3,3]，需合并为[1,5])。按升序排列 输出合并后的区间列表。
 * 输入描述: 一组区间列表，区间数为 N: 0<=N<=1000;区间元素为 X: -10000<=X<=10000。
 * 输出描述: 升序排列的合并区间列表
 * 备注:
 * 1、区间元素均为数字，不考虑字母、符号等异常输入。
 * 2、单个区间认定为无公共区间。
 * 示例:
 * 输入
 * [[0, 3], [1, 3], [3, 5], [3, 6]]
 * 输出
 * [[1, 5]]
 *
 *
 *  https://leetcode.cn/problems/merge-intervals/description/
 * @author 小八
 * @date 2023年02月11日15:43
 */
class Po{
    public int x;
    public int y;
    public Po(int x,int y){
        this.x = x ;
        this.y = y ;
    }
}
public class Title24 {

    public static void main(String[] args) {
        new Title24().merge1(new int[][]{{0,3},{1,3},{3,5},{3,6}});
    }

    public int[][] merge1(int[][] intervals){
        int n=intervals.length;
        Arrays.sort(intervals, (a,b)->{if(a[0]==b[0]){
            return a[1] - b[1];
        }else{
            return a[0] - b[0];
        }
        });
        List<Po> list = new ArrayList<>();
        Po p1 = new Po(intervals[0][0],intervals[0][1]);
        for(int i=1;i<n;i++){
            //存在交集
            if(p1.y >= intervals[i][0]){
                list.add(new Po(intervals[i][0],(p1.y>intervals[i][1])?(intervals[i][1]):(p1.y)));
            }
            p1.x = intervals[i][0];
            p1.y = intervals[i][1];
        }
        int[][] result = new int[list.size()][2];
        for(int i =0;i<list.size();i++){
            result[i][0] = list.get(i).x;
            result[i][1] = list.get(i).y;
        }
        return merge(result);
    }

    public int[][] merge(int[][] intervals) {
        int n=intervals.length;
        Arrays.sort(intervals, (a,b)->{if(a[0]==b[0]){
            return a[1] - b[1];
        }else{
            return a[0] - b[0];
        }
        });
        Deque<Po> deque = new ArrayDeque<>();
        for(int i=0;i<n;i++){
            if(deque.isEmpty()){
                deque.addLast(new Po(intervals[i][0],intervals[i][1]));
            }else{
                Po po = deque.removeFirst();
                if(po.y >= intervals[i][0] ){
                    if(po.y<intervals[i][1]){
                        po.y = intervals[i][1];
                    }

                    deque.addFirst(po);
                }else{
                    deque.addFirst(new Po(intervals[i][0],intervals[i][1]));
                    deque.add(po);
                }
            }
        }
        List<Po> list = new ArrayList<>(deque);
        Collections.sort(list, Comparator.comparingInt(a -> a.x));
        int[][] result = new int[list.size()][2];
        for(int i =0;i<list.size();i++){
            result[i][0] = list.get(i).x;
            result[i][1] = list.get(i).y;
        }
        return result;
    }
}
